#!/usr/bin/python3
# author luke
# 2024年02月01日
class Node():
    def __init__(self,elem = -1,lchild = None,rchild = None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild
class Tree():
    def __init__(self):
        self.root = None
        self.queue = []
    def insert_node(self,val):
       node =  Node(val)
       self.queue.append(node)
       if self.root == None:
           self.root = node
       else:
           if self.queue[0].lchild is None:
               self.queue[0].lchild = node
           elif self.queue[0].rchild is None:
               self.queue[0].rchild = node
               self.queue.pop(0)
    def preorder(self,current_node:Node):
        if current_node is None:
            return
        print(current_node.elem,end=' ')
        self.preorder(current_node.lchild)
        self.preorder(current_node.rchild)

# def preorder(T):
#     if T is None:
#         return
#     print(T.elem)
#     preorder(T.lchild)
#     preorder(T.rchild)
if __name__ == '__main__':
    tree = Tree()
    for i in range(1,11):
        tree.insert_node(i)
    tree.preorder(tree.root)